package algorithm.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * Description TODO
 *
 * @ClassName algorithm.sort.InsertSort
 * @Version 1.0
 * @Date: 2022/2/14 11:12
 * @Author xuyi
 */
public class InsertSort {
    @Test
    public void test1(){
        int[] arr = new int[]{1,5,3,4,2};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr){
        for(int i =1;i<arr.length;i++){
            //记录当前未排序元素cur
            int cur = arr[i];
            for(int j=i-1;j>=0;j--){
                //如果当前未排序元素比当前已排序元素小，则已排序元素后移一位
                if(cur<arr[j]){
                    arr[j+1]=arr[j];
                    if(j==0){
                        arr[j]=cur;
                    }
                }else{
                    //如果当前未排序元素大于等于当前已排序元素，则插入到当前已排序元素后面
                    arr[j+1]=cur;
                    break;
                }
            }
        }
    }

}
